Corelab Seminar
2017-2018
Stratis Ioannidis
Adaptive Caching Networks with Optimality Guarantees
Abstract.
Optimally placing content over a network of arises in many networking applications. Given the content demand, described by content requests and paths they follow, we wish to determine the content placement that maximizes the expected caching gain, i.e., the reduction of routing costs due to intermediate caching. The offline version of this problem is NP-hard. To make matters worse, in most cases, both the demand and the network topology may be a priori unknown; hence, distributed, adaptive content placement algorithms that yield constant approximation guarantees are desired. We show that path replication, an algorithm encountered often in both networking literature and in practice, can be arbitrarily suboptimal when combined with traditional cache eviction policies, like LRU, LFU, or FIFO. We propose a distributed, adaptive algorithm that provably constructs a probabilistic content placement within 1−1/e factor from the optimal, in expectation. Finally, we extend these results to optimizing caching and routing decisions jointly.